package distribution;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.TreeMap;

import utils.MainUtils;

import bbb.sss.Utils;

public class Combination<T> {

	private List<T> array;
	private List<List<T>> result = new ArrayList<List<T>>();
	private List<RangeCombination> threads = new ArrayList<RangeCombination>();

	public Combination(List<T> array) {
		this.array = array;
	}

	public List<List<T>> allCombination(int count, CombinationFilter<T> cf) {
		result.clear();
		long kkk = 0;
		if (count != 0) {
			long allCount = Utils.c(array.size(), count);
			for (long code = 1; code <= allCount; code++) {
				List<T> ss = new ArrayList<T>();
				fillListWithNull(ss, count);
				if (code <= allCount && code > 0) {
					long temp = code - 1;
					int curIndex = count;
					int position = array.size();
					while (curIndex > 0) {
						if (position > curIndex) {
							long ccc = Utils.c(position - 1, curIndex);
							if (ccc <= temp) {
								temp -= ccc;
								ss.set(curIndex - 1, array.get(position - 1));
								curIndex--;
							}
						} else {
							ss.set(curIndex - 1, array.get(position - 1));
							curIndex--;
						}
						position--;
					}
				}
				if (cf == null || cf.check(ss)) {
					result.add(ss);
					System.out.println(kkk++);
				}
			}
		}
		return result;
	}

	public List<List<T>> allCombination(int count) {
		return allCombination(count, null);
	}

	public List<List<T>> multipThreadAllCombination(int count, int threadCount,
			CombinationFilter<T> cf) {
		CombinationConfig config = MainUtils.readConfig();
		result.clear();
		threads.clear();
		if (count != 0) {
			long allCount = Utils.c(array.size(), count) - config.getFinishedCount();
			long threadTasks = (long) Math.ceil(allCount * 1.0 / threadCount);

			for (int i = 1; i <= threadCount; i++) {
				long start = threadTasks * (i - 1) + config.getFinishedCount();
				long end = threadTasks * i - 1 + config.getFinishedCount();
				if (i == threadCount) {
					end = allCount - 1;
				}
				System.out.println(start + ":" + end);
				RangeCombination rc = new RangeCombination(start, end, count,
						cf);
				threads.add(rc);
				new Thread(rc).start();
			}

			while (true) {
				synchronized (threads) {
					boolean allFinished = true;
					for (RangeCombination rc : threads) {
						if (!rc.isFinished) {
							allFinished = false;
							break;
						}
					}
					if (!allFinished) {
						try {
							threads.wait(5000);
						} catch (InterruptedException e) {
							e.printStackTrace();
						}
					} else {
						System.out.println("all finished");
						break;
					}
				}
			}
		}
		return result;
	}

	public static <T> void fillListWithNull(List<T> ss, long count) {
		if (ss != null) {
			for (long i = 0; i < count; i++) {
				ss.add(null);
			}
		}
	}

	public static <T> List<T> merge(List<T> c1, List<T> c2) {
		List<T> codes = new ArrayList<T>();
		TreeMap<T, T> mm = new TreeMap<T, T>();
		if (c1 != null) {
			for (T c : c1) {
				mm.put(c, c);
			}
		}
		if (c2 != null) {
			for (T c : c2) {
				mm.put(c, c);
			}
		}
		if (mm.size() > 0) {
			for (T code : mm.keySet()) {
				codes.add(code);
			}
		}
		return codes;
	}

	public static <T> List<T> substract(List<T> c1, List<T> c2) {
		if (c1 != null) {
			TreeMap<T, T> mm = new TreeMap<T, T>();
			for (T c : c1) {
				mm.put(c, c);
			}
			for (T c : c2) {
				if (mm.get(c) != null) {
					mm.remove(c);
				}
			}
			List<T> ret = new ArrayList<T>();
			for (T key : mm.keySet()) {
				ret.add(key);
			}
			return ret;
		}
		return null;
	}

	public static <T> List<T> asList(T[] array) {
		return Arrays.asList(array);
	}

	public static <T> Object[] asArray(List<T> list) {
		return list.toArray();
	}

	class RangeCombination implements Runnable {

		private long start;
		private long end;
		private int count;
		private CombinationFilter<T> cf;
		public boolean isFinished = false;

		public RangeCombination(long start, long end, int count,
				CombinationFilter<T> cf) {
			super();
			this.start = start;
			this.end = end;
			this.count = count;
			this.cf = cf;
		}

		@Override
		public void run() {
			for (long code = start; code <= end; code++) {
				List<T> ss = new ArrayList<T>();
				fillListWithNull(ss, count);
				long temp = code - 1;
				int curIndex = count;
				int position = array.size();
				while (curIndex > 0) {
					if (position > curIndex) {
						long ccc = Utils.c(position - 1, curIndex);
						if (ccc <= temp) {
							temp -= ccc;
							ss.set(curIndex - 1, array.get(position - 1));
							curIndex--;
						}
					} else {
						ss.set(curIndex - 1, array.get(position - 1));
						curIndex--;
					}
					position--;
				}
				if (cf == null || cf.check(ss)) {
					synchronized (result) {
						result.add(ss);
					}
				}
			}
			isFinished = true;
			synchronized (threads) {
				threads.notify();
			}
		}
	}

	public List<List<T>> getResult() {
		return result;
	}

}
